package de.hu.wbi.histoner;

import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
Copyright 2011,2012 Philippe Thomas
This file is part of histoner.

HistoNer is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
any later version.

HistoNer  is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with HistoNer .  If not, see <http://www.gnu.org/licenses/>.
*/

/**
 * Class used to optimize regular expressions for speed
 * @author solt
 *
 */
public class OptionalRegexOptimizer {

	String allowedChars =  "A-Za-z0-9 ";
	Pattern regexPattern = Pattern.compile("\\((["+ allowedChars + "\\|]+)\\)");
	Pattern splitPattern = Pattern.compile("\\|");

	
	/**
	 * Optimizes a regular expression
	 */
	public String optimize(String regex)
	{
	    
	    StringBuffer sb = new StringBuffer();
	    Matcher m = regexPattern.matcher(regex);
	    while (m.find())
	    {
		String optionalPart = m.group(1);
		String[] parts = splitPattern.split(optionalPart);
		KeywordTree t = new HashMapKeywordTree();
		for (String part : parts)
		{
		    t.add(part);
		}
		
		m.appendReplacement(sb, keywordTreeToRegex(t));
	    }
	    m.appendTail(sb);
	    return sb.toString();
	}

public static abstract class KeywordTree{
	
	public KeywordTree(){}

	/**
	 * Add a string to the keyword tree.
	 * Duplicates get ignored.
	 * @param str
	 */
	public abstract void add(String str);
	
	public abstract Collection<String> getPrefixes();
	
	public abstract KeywordTree getSubTree(String prefix);
	
	public abstract boolean isEmpty();
	
	public abstract boolean isDollar();
	
	public abstract boolean containsPrefix(String prefix);
	
	public char[] beginningChars()
	{
	    Set<Character> chars = new HashSet<Character>();
	    
	    for (String prefix : getPrefixes())
		chars.add(prefix.charAt(0));
	    
	    char[] res = new char[chars.size()];
	    int i = 0;
	    for (Character c : chars)
		res[i++] = c;
	    
	    return res;
	}
	
	};
	
	public static class HashMapKeywordTree extends KeywordTree{
	final HashMap<String, HashMapKeywordTree> tree;
	
	public HashMapKeywordTree()
	{
	    tree = new HashMap<String, HashMapKeywordTree>();
	}
	
	public HashMapKeywordTree(int sizeHint)
	{
	    tree = new HashMap<String, HashMapKeywordTree>(sizeHint);
	}
	
	
	@Override
	public void add(final String str) 
	{
	    if (str.isEmpty())
	    {
		tree.put("", null);
		return;
	    }
	    
	    if (tree.isEmpty())
	    {
		tree.put(str, Dollar());
		return;
	    }
		
	    for (String keyword : tree.keySet())
	    {
		int i;
		for (i = 0; i < Math.min(str.length(), keyword.length()) && (str.charAt(i) == keyword.charAt(i)); i++)
		{
		}
		
		// is keyword a prefix of str?
		if (i == keyword.length() && i> 0)
		{
		    tree.get(keyword).add(str.substring(keyword.length()));
		    return;
		}
		else if (i > 0)
		{
		    splitAt(keyword, str, i);
		    return;
		}
	    }
	    tree.put(str, Dollar());
	    
	}
	
	private void splitAt(String keyword, String str, int prefixLength)
	{
	    if (prefixLength <= 0)
		throw new IllegalArgumentException();
	    if (!str.startsWith(keyword.substring(0, prefixLength)))
		throw new IllegalArgumentException();
	    
	    final String prefix = keyword.substring(0, prefixLength);
	    final String keywordSuffix = keyword.substring(prefixLength);
	    final String strSuffix = str.substring(prefixLength);
	
	    final HashMapKeywordTree subTree = tree.get(keyword);
	    
	    final HashMapKeywordTree newTree = new HashMapKeywordTree();
	    newTree.tree.put(keywordSuffix, subTree);
	    newTree.tree.put(strSuffix, Dollar());
	    
	    
	    tree.remove(keyword);
	    tree.put(prefix, newTree);
	}
	
	private static HashMapKeywordTree Dollar()
	{
	    final HashMapKeywordTree res = new HashMapKeywordTree();
	    res.tree.put("", null);
	    return res; 
	}
	
	@Override
	public String toString()
	{
	    StringBuffer sb = new StringBuffer();
	    return toString(sb, 0).toString();
	}
	private StringBuffer toString(StringBuffer sb, int prefixLength)
	{
	    char[] padding = new char[prefixLength];
	    Arrays.fill(padding, '.');
	    for (String keyword : tree.keySet())
	    {
		sb.append(padding).append('"').append(keyword).append("\"\n");
		HashMapKeywordTree subTree = tree.get(keyword);
		if (subTree != null)
		    subTree.toString(sb, prefixLength + keyword.length());
	    }
	    return sb;
	}
	
	@Override
	public Collection<String> getPrefixes() {
	    return tree.keySet();
	}
	
	@Override
	public KeywordTree getSubTree(String prefix) {
	    return tree.get(prefix);
	}
	
	@Override
	public boolean isDollar() {
	    return (tree.size()== 1 && tree.containsKey(""));
	}
	
	@Override
	public boolean isEmpty() {
	    return tree.isEmpty();
	}
	
	@Override
	public boolean containsPrefix(String prefix) {
	    return tree.containsKey("");
	}
	}
	
	
	public String keywordTreeToRegex(KeywordTree t)
	{
	    StringBuffer sb = new StringBuffer();
	    return keywordTreeToRegex(t, sb).toString();
	}
	private StringBuffer keywordTreeToRegex(KeywordTree t, StringBuffer sb)
	{
	    if (t == null || t.isDollar())
		return sb;
	    
	    //char[] beginningChars = t.beginningChars();
	    
	
	    sb.append("(?:");
	    boolean isFirst = true;
	    boolean maybeEmpty = false;
	    for (String keyword : t.getPrefixes())
	    {
		if (keyword.isEmpty())
		{
		    maybeEmpty = true;
		    continue;
		}
		
		if (!isFirst)
		    sb.append('|');
		sb.append(keyword);
		KeywordTree subTree = t.getSubTree(keyword);
		keywordTreeToRegex(subTree, sb);
		
		isFirst = false;
	    }
	    sb.append(')');
	    if (maybeEmpty)
		sb.append('?');
	    return sb;
	}


}
